package lq1188;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
lq1188,LIS模板题，AC
注意输入优化 
 * */
public class Main {

	static int maxn = 600000;
	
	public static void main(String[] args) throws IOException {
		//输入数据量大，用BufferedReader
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] nums = br.readLine().split(" ");
		int[] a = new int[n+1];
		for(int i=1;i<=n;i++) {
			a[i] = Integer.parseInt(nums[i-1]);
		}
		System.out.println(lis2(a));
	}

	//最长上升子序列LIS（模板方法二，需用到二分查找，效率高O(nlogn)）
	//注意下标从1开始计算的
	static int[] d = new int[maxn];
	static int lis2(int[] a) {
		int len = 1;
		int n = a.length -1;
		d[1] = a[1];
		for(int i=2;i<=n;i++) {
			//与前一个数字相等的情况
			if(a[i] == d[len])
				continue;
			if(a[i] > d[len]) {
				//大于前一个数字的情况
				len++;
				d[len] = a[i];
			}else {
				//a[i]覆盖d中第一个大于a[i]的数
				int t = upperBound(1,len,a[i],d);
				d[t] = a[i];
			}
		}
		
		return len;
	}
	
	
	// 找到第一个大于target的元素的下标
	// 左开始下标l，右结束下标r，查询范围[l,r]
	// 如果target大于最大的数字，返回最大的数字的下标
	static int upperBound(int l, int r, int target, int[] a) {
	    while(l <= r){
	        int mid = (l+r)/2;
	        if(target>=a[mid]){
	            l = mid + 1;
	        }else {
	            r = mid - 1;
	        }
	    }
	    return l;
	}
}
